{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Distance to a Character"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: shortestToChar"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符的最短距离"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> 和一个字符 <code>c</code> ，且 <code>c</code> 是 <code>s</code> 中出现过的字符。</p>\n",
    "\n",
    "<p>返回一个整数数组 <code>answer</code> ，其中 <code>answer.length == s.length</code> 且 <code>answer[i]</code> 是 <code>s</code> 中从下标 <code>i</code> 到离它 <strong>最近</strong> 的字符 <code>c</code> 的 <strong>距离</strong> 。</p>\n",
    "\n",
    "<p>两个下标&nbsp;<code>i</code> 和 <code>j</code> 之间的 <strong>距离</strong> 为 <code>abs(i - j)</code> ，其中 <code>abs</code> 是绝对值函数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"loveleetcode\", c = \"e\"\n",
    "<strong>输出：</strong>[3,2,1,0,1,0,0,1,2,2,1,0]\n",
    "<strong>解释：</strong>字符 'e' 出现在下标 3、5、6 和 11 处（下标从 0 开始计数）。\n",
    "距下标 0 最近的 'e' 出现在下标 3 ，所以距离为 abs(0 - 3) = 3 。\n",
    "距下标 1 最近的 'e' 出现在下标 3 ，所以距离为 abs(1 - 3) = 2 。\n",
    "对于下标 4 ，出现在下标 3 和下标 5 处的 'e' 都离它最近，但距离是一样的 abs(4 - 3) == abs(4 - 5) = 1 。\n",
    "距下标 8 最近的 'e' 出现在下标 6 ，所以距离为 abs(8 - 6) = 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaab\", c = \"b\"\n",
    "<strong>输出：</strong>[3,2,1,0]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "<strong>提示：</strong>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>s[i]</code> 和 <code>c</code> 均为小写英文字母</li>\n",
    "\t<li>题目数据保证 <code>c</code> 在 <code>s</code> 中至少出现一次</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-distance-to-a-character](https://leetcode.cn/problems/shortest-distance-to-a-character/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-distance-to-a-character](https://leetcode.cn/problems/shortest-distance-to-a-character/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"loveleetcode\"\\n\"e\"', '\"aaab\"\\n\"b\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        # 计算c右边的\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                idx = i\n",
    "            ans[i] = i - idx\n",
    "        \n",
    "        idx = 2 * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            ans[i] = min(ans[i], idx - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [n] * n  # 初始化 ans 列表为最大值 n\n",
    "        \n",
    "        # 从左向右遍历，更新字符 c 的左边距离\n",
    "        prev = -n\n",
    "        for i in range(n):\n",
    "            if s[i] == c:\n",
    "                prev = i\n",
    "            ans[i] = min(ans[i], i - prev)\n",
    "        \n",
    "        # 从右向左遍历，更新字符 c 的右边距离\n",
    "        prev = 2 * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                prev = i\n",
    "            ans[i] = min(ans[i], prev - i)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        # 思路： 统计c在s中的索引，遍历s，取绝对值最小的值\n",
    "        # 统计c在s的所有索引\n",
    "        # ans = []\n",
    "        # find_all = lambda strings,string: [i for i in range(len(s)) if s[i] == string] # lambda返回函数对象，\n",
    "        # i_lis = find_all(s, c)\n",
    "        # # 遍历 s和 i_lis, 输出最小绝对值\n",
    "        # for m in range(len(s)):\n",
    "        #     count = []\n",
    "        #     for n in range(len(i_lis)):\n",
    "        #         count.append(abs(m-i_lis[n]))\n",
    "        #     ans.append(min(count))\n",
    "        # return ans\n",
    "\n",
    "        c_idx = [i for i in range(len(s)) if s[i] == c]\n",
    "        return [min(abs(m-n) for n in c_idx) for m in range(len(s))]\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        length = len(s)\n",
    "        c_index = []\n",
    "        for i in range(length):\n",
    "            if s[i] == c:\n",
    "                c_index.append([abs(j-i) for j in range(length)])\n",
    "        ret = [min([c_index[i][j] for i in range(len(c_index))]) for j in range(length)]\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        res=[-1]*len(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==c:\n",
    "                res[i]=0\n",
    "        for i in range(res.index(0),len(res)):\n",
    "            if res[i]==0:\n",
    "                j=0\n",
    "            res[i]=j\n",
    "            j+=1\n",
    "        ser=res[::-1]\n",
    "        for i in range(ser.index(0),len(ser)):\n",
    "            if ser[i]==0:\n",
    "                j=0\n",
    "            res[len(res)-i-1]=min(res[len(res)-i-1],j)\n",
    "            j+=1\n",
    "        for i in range(res.index(0),-1,-1):\n",
    "            if res[i]==0:\n",
    "                j=0\n",
    "            res[i]=j\n",
    "            j+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        c_l = [idx for idx, s_ in enumerate(s) if s_ == c]\n",
    "        l = []\n",
    "        for idx, s_ in enumerate(s):\n",
    "            if s_ == c:\n",
    "                l.append(0)\n",
    "            else:\n",
    "                l.append(min(abs(i - idx) for i in c_l))\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n=len(s)\n",
    "        res=[0]*n\n",
    "\n",
    "        idx=-n\n",
    "        for i in range(n):\n",
    "            if s[i]==c:\n",
    "                idx=i\n",
    "            res[i]=i-idx\n",
    "        \n",
    "        idx=2*n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i]==c:\n",
    "                idx=i\n",
    "            res[i]=min(res[i],idx-i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        a=[]\n",
    "        b=len(s)\n",
    "        for i in range(len(s)):\n",
    "            if c in s[i:]:\n",
    "                d=s[i:].index(c)\n",
    "                if c==s[i]:\n",
    "                    b=0\n",
    "            else:\n",
    "                d=len(s)\n",
    "            a.append(min(b,d))\n",
    "            b=b+1 if b!=len(s) else b\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        s=list(s)\n",
    "        n=len(s)\n",
    "        ans=[0]*n\n",
    "        for i,x in enumerate(s):\n",
    "            l=r=i\n",
    "            while(1):\n",
    "                if s[l]==c:\n",
    "                    ans[i]=i-l\n",
    "                    break\n",
    "                if s[r]==c:\n",
    "                    ans[i]=r-i\n",
    "                    break\n",
    "                l=l-1 if l>0 else 0\n",
    "                r=r+1 if r<n-1 else n-1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        res = [0] * n\n",
    "        index = -n - 1\n",
    "        for i in range(n):\n",
    "            if s[i] == c:\n",
    "                index = i\n",
    "            res[i] = i - index\n",
    "        index = n * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            # print(res)\n",
    "            if s[i] == c:\n",
    "                index = i\n",
    "            res[i] = min(res[i], index - i)\n",
    "        return res\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        arr=[]\n",
    "        ans=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] ==c:\n",
    "                arr.append(i)\n",
    "        # print(arr)\n",
    "        for j in range(len(s)):\n",
    "            tmp=[]\n",
    "            for k in arr:\n",
    "                tmp.append(abs((j-k)))\n",
    "            ans.append(min(tmp))\n",
    "        # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        c_pos = [i for i, v in enumerate(s) if v == c]\n",
    "        return [min(abs(p - i) for p in c_pos) for i, x in enumerate(s)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        # 两次遍历，一次从左，一次从右\n",
    "        n = len(s)\n",
    "        ans = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                idx = i\n",
    "            ans[i] = i - idx  # 左侧最近的\n",
    "            \n",
    "        idx = 2 * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            ans[i] = min(ans[i], idx - i)  # 右侧最近的与左侧最近的比较\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        # 思路： 统计c在s中的索引，遍历s，取绝对值最小的值\n",
    "        # 统计c在s的所有索引\n",
    "        ans = []\n",
    "        find_all = lambda strings,string: [i for i in range(len(s)) if s[i] == string] # lambda返回函数对象，\n",
    "        i_lis = find_all(s, c)\n",
    "        # 遍历 s和 i_lis, 输出最小绝对值\n",
    "        for m in range(len(s)):\n",
    "            count = []\n",
    "            for n in range(len(i_lis)):\n",
    "                count.append(abs(m-i_lis[n]))\n",
    "            ans.append(min(count))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "class Solution:\r\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\r\n",
    "        prev, next = -1, -1\r\n",
    "        i, n = 0, len(s)\r\n",
    "        res = [0] * n\r\n",
    "        while i < n:\r\n",
    "            if prev < 0:\r\n",
    "                if s[i] == c:\r\n",
    "                    res[i] = 0\r\n",
    "                    prev += 1\r\n",
    "                    while prev < i:\r\n",
    "                        res[prev] = i - prev\r\n",
    "                        prev += 1   \r\n",
    "                i += 1\r\n",
    "            else:\r\n",
    "                if s[i] != c:\r\n",
    "                    res[i] = i - prev      \r\n",
    "                else:\r\n",
    "                    res[i] = 0\r\n",
    "                    prev += 1\r\n",
    "                    while prev < i:\r\n",
    "                        res[prev] = min(res[prev], i - prev)\r\n",
    "                        prev += 1   \r\n",
    "                i += 1\r\n",
    "        return res                            \r\n",
    "s = \"loveleetcode\"\r\n",
    "c = \"e\"\r\n",
    "print(Solution().shortestToChar(s, c))\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                idx = i\n",
    "            ans[i] = i - idx\n",
    "\n",
    "        idx = 2 * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            ans[i] = min(ans[i], idx - i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        \"\"\"\n",
    "        对于第一个c前面的字符 显然最近就是和第一个c最近的距离 \n",
    "        重点是两个c之间的字符就需要单独考虑 显然可以算两个c的中间位置中心位置左侧就是第一个c 否则第二个c \n",
    "        \"\"\"\n",
    "        c_index = [] #记录每个下标的位置\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==c:\n",
    "                c_index.append(i)\n",
    "        c_index.append(len(s)*2) #添加一个虚拟c下标 这样便于后续统一处理\n",
    "        upBound = (c_index[0]+c_index[1])//2 #当前上界\n",
    "        idIndex = 0 #在当前范围内需要比较index的下标\n",
    "        rs = [0 for _ in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            if i>upBound:\n",
    "                idIndex += 1\n",
    "                upBound = (c_index[idIndex]+c_index[idIndex+1])//2 #永远不会越界 因为最后一个上界是没法超过的\n",
    "            if s[i]==c:\n",
    "                continue\n",
    "            rs[i] = abs(c_index[idIndex]-i)\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n=len(s)\n",
    "        res=[0]*n\n",
    "\n",
    "        idx=-n\n",
    "        for i in range(n):\n",
    "            if s[i]==c:\n",
    "                idx=i\n",
    "            res[i]=i-idx\n",
    "        \n",
    "        idx=2*n\n",
    "        for i in range(-1,-1-n,-1):\n",
    "            if s[i]==c:\n",
    "                idx=i\n",
    "            res[i]=min(res[i],idx-i)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "\n",
    "        a,b=[],[]\n",
    "\n",
    "        for i in range(len(s)):\n",
    "\n",
    "            if s[i]==c:\n",
    "\n",
    "                a.append(i)\n",
    "\n",
    "        for i in range(len(s)):\n",
    "\n",
    "            ans=float('inf')\n",
    "\n",
    "            if s[i]!=c:\n",
    "\n",
    "                for j in a:\n",
    "\n",
    "                    ans=min(ans,abs(i-j))\n",
    "\n",
    "                b.append(ans)\n",
    "\n",
    "            elif s[i]==c:\n",
    "\n",
    "                b.append(0)\n",
    "\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        ans, last = [inf] * len(s), -inf\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                last = i\n",
    "            ans[i] = min(ans[i], i - last)\n",
    "        last = inf\n",
    "        for i, ch in enumerate(s[::-1]):\n",
    "            # 因为两者都有 len(s) - 1 的偏移量，可以一起去掉，减少运算            \n",
    "            # if ch == c:\n",
    "            #     last = len(s) - 1 - i\n",
    "            # ans[-1 - i] = min(ans[-1 - i], last - len(s) + 1 + i)\n",
    "            if ch == c:\n",
    "                last = -i\n",
    "            ans[-1 - i] = min(ans[-1 - i], last + i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                idx = i\n",
    "            ans[i] = i - idx\n",
    "\n",
    "        idx = 2 * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            ans[i] = min(ans[i], idx - i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        rst = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, v in enumerate(s):\n",
    "            if v == c:\n",
    "                idx = i\n",
    "            rst[i] = i - idx\n",
    "\n",
    "        idx = 2 * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            rst[i] = min(rst[i], idx - i)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        c_l = [idx for idx, s_ in enumerate(s) if s_ == c]\n",
    "        l = []\n",
    "        for idx, s_ in enumerate(s):\n",
    "            if s_ == c:\n",
    "                l.append(0)\n",
    "            else:\n",
    "                l.append(min(abs(i - idx) for i in c_l))\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        pl = []\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                pl.append(i)\n",
    "        # print(pl)\n",
    "        ret = [0] * len(s)\n",
    "        for i in range(len(s)):\n",
    "            if i not in pl:\n",
    "                ret[i] = min(abs(i - x) for x in pl)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        res = [i for i in range(len(s)) if s[i]==c]\n",
    "        res2 = []\n",
    "        for j in range(len(s)):\n",
    "            res2.append(min([abs(j - i) for i in res]))\n",
    "        return res2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        res = []\n",
    "        lastindex = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == c:\n",
    "                res.append(0)\n",
    "                lastindex = i\n",
    "            else:\n",
    "                res.append(min(abs(s.find(c,i)-i), abs(s.find(c,lastindex)-i)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        c_index = [i for i in range(len(s)) if s[i] == c]\n",
    "        distance = []\n",
    "        for i in range(len(s)):\n",
    "            min_ = min([abs(i-j) for j in c_index])\n",
    "            distance.append(min_)\n",
    "        return distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        # 两次遍历，一次从左，一次从右\n",
    "        n = len(s)\n",
    "        ans = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                idx = i\n",
    "            ans[i] = i - idx  # 左侧最近的\n",
    "\n",
    "        idx = 2 * n   # 从后往前，对于最后一个元素，其右侧应该跟他保持n及以上的距离，如果是n的话就相当于认为最后一位的右侧就是目标字符\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            ans[i] = min(ans[i], idx - i)  # 右侧最近的与左侧最近的比较\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [inf] * n\n",
    "        cnt = inf\n",
    "        for i, char in enumerate(s):\n",
    "            if char == c:\n",
    "                cnt = 0\n",
    "            else:\n",
    "                cnt += 1\n",
    "            if cnt < ans[i]:\n",
    "                ans[i] = cnt\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                cnt = 0\n",
    "            else:\n",
    "                cnt += 1\n",
    "            if cnt < ans[i]:\n",
    "                ans[i] = cnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        ans = [inf] * len(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == c:\n",
    "                for j in range(len(s)):\n",
    "                    if ans[j] > abs(i-j):\n",
    "                        ans[j] = abs(i-j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        # 两次遍历，一次从左，一次从右\n",
    "        n = len(s)\n",
    "        ans = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                idx = i\n",
    "            ans[i] = i - idx  # 左侧最近的\n",
    "\n",
    "        idx = 2 * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            ans[i] = min(ans[i], idx - i)  # 右侧最近的与左侧最近的比较\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        pl = []\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                pl.append(i)\n",
    "        # print(pl)\n",
    "        ret = [0] * len(s)\n",
    "        # for i in range(len(s)):\n",
    "        #     if i not in pl:\n",
    "        #         ret[i] = min(abs(i - x) for x in pl)\n",
    "        # 分为三段。第一个字符之前，两个字符之间，最后一个字符之后\n",
    "        for i in range(pl[0]):\n",
    "            ret[i] = pl[0] - i\n",
    "        for i in range(len(pl) - 1):\n",
    "            l, r = pl[i], pl[i + 1]\n",
    "            for j in range(l, r):\n",
    "                ret[j] = min(j - l, r - j)\n",
    "        for i in range(pl[-1], len(s)):\n",
    "            ret[i] = i - pl[-1]\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        temp=[]\n",
    "        length=len(s)\n",
    "        for i in range(length):\n",
    "            if s[i]==c:\n",
    "                temp.append(i)\n",
    "        answer=[length]*length\n",
    "        for i in temp:\n",
    "            left=right=i\n",
    "            answer[i]=0\n",
    "            count=0\n",
    "            while left>0:\n",
    "                left-=1\n",
    "                count+=1\n",
    "                answer[left]=min(answer[left],count)\n",
    "            count=0\n",
    "            while right<length-1:\n",
    "                right+=1\n",
    "                count+=1\n",
    "                answer[right]=min(answer[right],count)\n",
    "            count=0\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n=len(s)\n",
    "        idx=-9999\n",
    "        ans=[0]*n\n",
    "        for i,ch in enumerate(s):\n",
    "            if ch==c:\n",
    "                idx=i\n",
    "            ans[i]=i-idx\n",
    "        idx=9999\n",
    "        for i in range(n-1,-1,-1):\n",
    "            if s[i]==c:\n",
    "                idx=i\n",
    "            ans[i]=min(ans[i],idx-i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        c_indexes = []\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == c:\n",
    "                c_indexes.append(i)\n",
    "        for i in range(len(s)):\n",
    "            res.append(min([abs(i-x)  for x in c_indexes]))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        temp = []\n",
    "        for index, i in enumerate(s):\n",
    "            if i == c:\n",
    "                temp.append(index)\n",
    "        res = []\n",
    "        for index in range(len(s)):\n",
    "            dic = []\n",
    "            for i in temp:\n",
    "                dic.append(abs(index - i))\n",
    "            res.append(min(dic))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef shortestToChar(self, S, C):\n",
    "\t\ta, p = [1000000000] * len(S), -1\n",
    "\t\tfor i in range(len(S)):\n",
    "\t\t\tif S[i] == C: p = i\n",
    "\t\t\tif p >= 0: a[i] = min(a[i], i - p)\n",
    "\t\tp = -1\n",
    "\t\tfor i in range(len(S) - 1, -1, -1):\n",
    "\t\t\tif S[i] == C: p = i\n",
    "\t\t\tif p >= 0: a[i] = min(a[i], p - i)\n",
    "\t\treturn a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ansss(self,j,a):\n",
    "        minans = 10001\n",
    "        for m in a:\n",
    "            ans = abs(m-j)\n",
    "            if ans <= minans:\n",
    "                minans = ans\n",
    "        return minans\n",
    "\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        a =[]\n",
    "        b =[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == c :\n",
    "                a.append(i)\n",
    "        for j in range(len(s)):\n",
    "            ans = self.ansss(j,a)\n",
    "            #ans = min(abs(m-j for m in a))\n",
    "            b.append(ans)\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        rst = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, v in enumerate(s):\n",
    "            if v == c:\n",
    "                idx = i\n",
    "            rst[i] = i - idx\n",
    "        \n",
    "        idx = 2 * n \n",
    "        for i in reversed(range(n)):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            rst[i] = min(rst[i], idx - i)\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                idx = i\n",
    "            ans[i] = i - idx\n",
    "        \n",
    "        idx = float('inf')\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            ans[i] = min(ans[i], idx - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        ans = [len(s) for _ in range(len(s))]\n",
    "        c_index = []\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                c_index.append(i)\n",
    "        for index in c_index:\n",
    "            ans = [min(num, abs(i-index)) for i, num in enumerate(ans)]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        res = [len(s)] * len(s)\n",
    "        for i in range(0,len(s)):\n",
    "            pre = res[i - 1] + 1 \n",
    "            if s[i] == c:\n",
    "                res[i] = 0\n",
    "            else:\n",
    "                res[i] = pre\n",
    "\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if 0 <= i+1 < len(s):\n",
    "                res[i] = min(res[i], res[i+1]+1)\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        result=[0]*len(s)\n",
    "        last=-1\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==c:\n",
    "                if last==-1:\n",
    "                    for j in range(0,i):\n",
    "                        result[j]=i-j\n",
    "                else:\n",
    "                    for j in range(last+1,i):\n",
    "                        result[j]=min(i-j,j-last)\n",
    "                last=i\n",
    "        for i in range(last+1,len(s)):\n",
    "            result[i]=i-last\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        sd=[len(s)]*len(s)\n",
    "\n",
    "        idx=None\n",
    "        for i, ch in enumerate(s):\n",
    "            if idx is not None:\n",
    "                sd[i]=i-idx\n",
    "            if ch == c:\n",
    "                sd[i]=0\n",
    "                idx=i\n",
    "        idx=None\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if idx is not None:\n",
    "                sd[i]=min(sd[i],idx-i) #二次遍历取小\n",
    "            if s[i]==c:\n",
    "                # sd[i]=0\n",
    "                idx=i\n",
    "\n",
    "        return sd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        pl = []\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                pl.append(i)\n",
    "        # print(pl)\n",
    "        ret = [0] * len(s)\n",
    "        for i in range(len(s)):\n",
    "            ret[i] = min(abs(i - x) for x in pl)\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                idx = i\n",
    "            ans[i] = i - idx\n",
    "\n",
    "        idx = 2 * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            ans[i] = min(ans[i], idx - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [999999 for _ in range(n)]\n",
    "        l = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == c:\n",
    "                l = i\n",
    "                break\n",
    "        \n",
    "        for i in range(n):\n",
    "            if s[i] == c:\n",
    "                ans[i] = 0\n",
    "                l = i\n",
    "            else:\n",
    "                ans[i] = abs(l - i)\n",
    "        \n",
    "        r = n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                r = i\n",
    "                break\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                r = i\n",
    "            else:\n",
    "                ans[i] = min(ans[i], abs(i - r))\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        x=[]\n",
    "        y=[]\n",
    "        n=len(s)\n",
    "        for i in range(n):\n",
    "            if s[i]==c:\n",
    "                x.append(i)\n",
    "        for j in range(n):\n",
    "            z=[]\n",
    "            if j in x:\n",
    "                y.append(0)\n",
    "            if j not in x:\n",
    "                for k in x:\n",
    "                    z.append(abs(j-k))\n",
    "                y.append(min(z))\n",
    "        return y\n",
    "       \n",
    "\n",
    "           \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def diff(n):\n",
    "        return \n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        r = []\n",
    "        res = []\n",
    "        m = 100000\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == c:\n",
    "                r.append(i)\n",
    "            \n",
    "        for i in range(len(s)):\n",
    "            for j in range(len(r)):\n",
    "                if m> abs( r[j]-i)  :\n",
    "                    m=abs( r[j]-i)\n",
    "            res.append(m)\n",
    "            m=10000\n",
    "        return res\n",
    "\n",
    "\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        indexes = [i for i in range(n) if s[i] == c]\n",
    "        ans = [inf] * n\n",
    "        for i in range(n):\n",
    "            idx = bisect_left(indexes, i)\n",
    "            if idx < len(indexes):\n",
    "                ans[i] = abs(i - indexes[idx])\n",
    "            if idx + 1 < len(indexes):\n",
    "                ans[i] = min(ans[i], indexes[idx + 1] - i)\n",
    "            if idx - 1 >= 0:\n",
    "                ans[i] = min(ans[i], i - indexes[idx - 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [0] * n\n",
    "        idx = -n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                idx = i\n",
    "            ans[i] = i - idx\n",
    "        idx = 2 * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            ans[i] = min(ans[i], idx - i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        res = [0 if ch == c else n for ch in s]\n",
    "\n",
    "        for i in range(1 , n):\n",
    "            res[i] = min(res[i] , res[i-1] + 1)\n",
    "        for i in range(n-2, -1, -1):\n",
    "            res[i] = min(res[i], res[i + 1] + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        ans = [0]*len(s)\n",
    "        idx = -len(s)\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==c:\n",
    "                idx = i \n",
    "            ans[i]=i-idx \n",
    "        idx = 2*len(s)\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            if s[i]==c:\n",
    "                idx = i \n",
    "            ans[i]=min(ans[i],idx-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        dis = [0] * n\n",
    "        left, right = float(\"-inf\"), float(\"-inf\")\n",
    "        p = 0\n",
    "        for i in range(n):\n",
    "            if s[i] == c:\n",
    "                left = right\n",
    "                right = i\n",
    "                for k in range(p, right):\n",
    "                    dis[k] = min(abs(left-k), abs(right - k))\n",
    "                p = right + 1\n",
    "        for k in range(p,n):\n",
    "            dis[k] = min(abs(left-k), abs(right - k))\n",
    "\n",
    "        return dis"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        ref = [-10**4]\n",
    "        for i,a in enumerate(s):\n",
    "            if a==c:\n",
    "                ref.append(i)\n",
    "        ref.append(2*10**4)\n",
    "        j = 0\n",
    "        res = []\n",
    "        for i,a in enumerate(s):\n",
    "            res.append(min(abs(i-ref[j]),abs(ref[j+1]-i)))\n",
    "            if i == ref[j+1]:\n",
    "                j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        index = []\n",
    "        res = [i for i in range(len(s))]\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == c:\n",
    "                index.append(i)\n",
    "        for j in range(len(s)):\n",
    "            res[j] = min([abs(index[k]-res[j]) for k in range(len(index))])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        l=[]\n",
    "        for i in range(len(s)):\n",
    "            if s[i]==c:\n",
    "                l.append(i)\n",
    "        res=[]\n",
    "        for i in range(len(s)):\n",
    "            a=100000000000\n",
    "            for j in range(len(l)):\n",
    "                a=min(a,abs(i-l[j]))\n",
    "            res.append(a)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [n + 1] * n\n",
    "        j = -1\n",
    "        for i, si in enumerate(s):\n",
    "            if si == c:\n",
    "                j = i\n",
    "            if j != -1:\n",
    "                ans[i] = i - j\n",
    "        j = -1\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                j = i\n",
    "            if j != -1:\n",
    "                ans[i] = min(ans[i], j - i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                idx = i\n",
    "            ans[i] = i - idx\n",
    "\n",
    "        idx = 2 * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            ans[i] = min(ans[i], idx - i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        c_set = set()\n",
    "        ans = []\n",
    "        # find place\n",
    "        for i, ci in enumerate(s):\n",
    "            if ci == c:\n",
    "                c_set.add(i)\n",
    "\n",
    "        # loop s, find each distance\n",
    "        for i, si in enumerate(s):\n",
    "            cur_min = len(s) + 1\n",
    "            for j in c_set:\n",
    "                cur_min = min(cur_min, abs(i - j))\n",
    "            ans.append(cur_min)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 一刷\n",
    "class Solution:\n",
    "    def shortestToChar(self, S: str, C: str) -> List[int]:\n",
    "        # 暴力获取C字符的索引，遍历获取每个字符串的最小距离\n",
    "        return [min(abs(i- j)  for j in [i for i in range(len(S)) if S[i] == C]) for i in range(len(S))]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            ccc = 999\n",
    "            for k in range(len(s)):\n",
    "                if s[k] == c:\n",
    "                    ccc = min(ccc,abs(i-k))\n",
    "            res.append(ccc)\n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        x=[]\n",
    "        y=[]\n",
    "        n=len(s)\n",
    "        for i in range(n):\n",
    "            if s[i]==c:\n",
    "                x.append(i)\n",
    "        for j in range(n):\n",
    "            z=[]\n",
    "            if j in x:\n",
    "                y.append(0)\n",
    "            if j not in x:\n",
    "                for k in x:\n",
    "                    a=abs(j-k)\n",
    "                    z.append(a)\n",
    "                b=min(z)\n",
    "                y.append(b)\n",
    "        return y\n",
    "       \n",
    "\n",
    "           \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        ret, p, arr = [], 0, [i for i in range(len(s)) if s[i] == c]\n",
    "        for i, j in enumerate(s):\n",
    "            if p < len(arr) - 1 and abs(arr[p] - i) > abs(arr[p + 1] - i):\n",
    "                p += 1\n",
    "            ret.append(abs(arr[p] - i))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        ans = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                idx = i\n",
    "            ans[i] = i - idx\n",
    "\n",
    "        idx = 2 * n\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            ans[i] = min(ans[i], idx - i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        # aim =[]\n",
    "        # for i in range(len(s)):\n",
    "        #     if s[i] == c:\n",
    "        #         aim.append(i)\n",
    "        # # [3,5,6,11]\n",
    "        # \n",
    "        # for i in range(len(s)):\n",
    "        #     for j in range(len(aim)):\n",
    "        #         if i in aim:\n",
    "        #             l.append(0)\n",
    "        #         elif i<\n",
    "        l = []\n",
    "        for x in range(len(s)):\n",
    "            if s[x] == c:\n",
    "                l.append(0)\n",
    "                continue\n",
    "            i=x-1\n",
    "            j=x+1\n",
    "            while i>=0 or j<len(s):\n",
    "                if i>=0:\n",
    "                    if s[i] == c:\n",
    "                        l.append(abs(x-i))\n",
    "                        break\n",
    "                    else:\n",
    "                        i-=1\n",
    "                if j<len(s):\n",
    "                    if s[j] == c:\n",
    "                        l.append(abs(j-x))\n",
    "                        break\n",
    "                    else:\n",
    "                        j+=1\n",
    "\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        sl = len(s)\n",
    "        res = [0 for i in range(0, sl)]\n",
    "        temp = [inf]\n",
    "        for i in range(0, sl):\n",
    "            if s[i] == c:\n",
    "                temp.append(i)\n",
    "        tl = len(temp)\n",
    "        j = 1\n",
    "        for i in range(0, sl):\n",
    "            if i > temp[j]:\n",
    "                j = min(j + 1, tl-1)\n",
    "            res[i] = min(abs(i - temp[j]), abs(i - temp[j-1]))\n",
    "        print(temp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        ans, last = [inf] * len(s), None\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == c:\n",
    "                if last is not None:\n",
    "                    for j in range(i, (i - 1 + last) // 2 - 1, -1):\n",
    "                        ans[j] = min(ans[j], i - j)\n",
    "                else:\n",
    "                    for j in range(i, -1, -1):\n",
    "                        ans[j] = min(ans[j], i - j)\n",
    "                last = i\n",
    "            elif last is not None:\n",
    "                ans[i] = min(ans[i], i - last)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, S: str, C: str) -> List[int]:\n",
    "        n = len(S)\n",
    "        # 字母向左和向右，是c字符的距离为0\n",
    "        res = [0 if c == C else n for c in S]\n",
    "\n",
    "        # 向右\n",
    "        for i in range(1, n):\n",
    "           res[i] = min(res[i], res[i - 1] + 1)\n",
    "        # 向左\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            res[i] = min(res[i], res[i + 1] + 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        a = []\n",
    "        b = []\n",
    "        for i,j in enumerate(s):\n",
    "            if j == c:\n",
    "                a.append(i)\n",
    "        for k in range(len(s)):\n",
    "            c = len(s)\n",
    "            for m in range(len(a)):\n",
    "                c = min(c,abs(k-a[m]))\n",
    "            b.append(c)\n",
    "        return b \n",
    "            \n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 一刷\n",
    "class Solution:\n",
    "    def shortestToChar(self, S: str, C: str) -> List[int]:\n",
    "        # 暴力获取C字符的索引，遍历获取每个字符串的最小距离\n",
    "        return [min(abs(i- j)  for j in [i for i in range(len(S)) if S[i] == C]) for i in range(len(S))]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def shortestToChar(self, s: str, c: str) -> List[int]:\n",
    "        n = len(s)\n",
    "        rst = [0] * n\n",
    "\n",
    "        idx = -n\n",
    "        for i, v in enumerate(s):\n",
    "            if v == c:\n",
    "                idx = i\n",
    "            rst[i] = i - idx\n",
    "\n",
    "        idx = 2 * n\n",
    "        for i in range(n-1, -1, -1):\n",
    "            if s[i] == c:\n",
    "                idx = i\n",
    "            rst[i] = min(rst[i], idx - i)\n",
    "\n",
    "        return rst"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
